import tool.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个链表的头节点head，请你编写代码，反复删去链表中由 总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
 *
 * 删除完毕后，请你返回最终结果链表的头节点。
 *
 * 你可以返回任何满足题目要求的答案。
 *
 * （注意，下面示例中的所有序列，都是对ListNode对象序列化的表示。）
 *
 * 示例 1：
 * 输入：head = [1,2,-3,3,1]
 * 输出：[3,1]
 * 提示：答案 [1,2,1] 也是正确的。
 *
 * 示例 2：
 * 输入：head = [1,2,3,-3,4]
 * 输出：[1,2,4]
 *
 * 示例 3：
 * 输入：head = [1,2,3,-3,-2]
 * 输出：[1]
 *
 * 提示：
 * 给你的链表中可能有 1 到1000个节点。
 * 对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01171m {

    public ListNode removeZeroSumSublists(ListNode head) {
        int sum = 0; // 前缀和
        ListNode hair = new ListNode(0);
        hair.next = head;
        Map<Integer, ListNode> map = new HashMap<>();
        map.put(0, hair);
        while (head != null) {
            sum += head.val;
            ListNode node = map.get(sum);
            if (node == null) {
                map.put(sum, head);
            } else {
                ListNode curr = node.next;
                int preSum = sum;
                while (curr != head) { // 删除两次相等和之间的所有节点
                    map.remove(preSum += curr.val);
                    curr = curr.next;
                }
                node.next = head.next; // 取出和为0的区间的引用
            }
            head = head.next;
        }
        return hair.next;
    }
}
